public class Test14 {
    // 只用一个 dp 表
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n + 1][3];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == 0) dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
                if (j == 1) dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
                if (j == 2) dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
    }
    //使用两个 dp 表
    public int minCost1(int[][] costs) {
        int n = costs.length;

        int[][] T = new int[n][3];
        int[][] F = new int[n][3];

        for(int i = 0;i < 3;i++) {
            T[0][i] = costs[0][i];
        }
        F[0][0] = Math.min(T[0][1],T[0][2]);
        F[0][1] = Math.min(T[0][0],T[0][2]);
        F[0][2] = Math.min(T[0][0],T[0][1]);

        for(int i = 1;i < n;i++) {
            for(int j = 0;j < 3;j++) {
                T[i][j] = costs[i][j] + F[i - 1][j];

            }

            for(int j = 0;j < 3;j++) {
                if(j == 0) F[i][0] = Math.min(T[i][1],T[i][2]);
                if(j == 1) F[i][1] = Math.min(T[i][0],T[i][2]);
                if(j == 2) F[i][2] = Math.min(T[i][0],T[i][1]);
            }
        }

        for(int i = 0; i < n;i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(T[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
        for(int i = 0; i < n;i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(F[i][j] + " ");
            }
            System.out.println();
        }
        return Math.min(Math.min(T[n - 1][0],T[n - 1][1]),T[n - 1][2]);
    }

    public static void main(String[] args) {
        Test14 test14 = new Test14();
        int[][] arr = {{17,2,17},{16,16,5},{14,3,19}};
        System.out.println(test14.minCost(arr));
    }
}
